package dynamicProgramming.SingleSequenceProblem;

import java.util.Arrays;

/**
 * @author zxc
 * @date 2023/01/19 09:27
 **/
/**
 *  题目 ：房屋偷盗问题
 *  题目详情 ：
 *  一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 *  如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *  给定一个代表每个房屋存放金额的非负整数数组 nums，请计算不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 *  1 <= nums.length <= 100
 * 0 <= nums[i] <= 400
 */
public class Rob_iteration {
    /**
     * 思路 ：
     * （1）创建大小和nums数组一致的redis数组（用来存储 从标号0到标号i的房屋为止最多能够偷取到财物的最大值）;
     * （2）在进行迭代之前,先对于隐性条件 i >= 2进行满足;
     * （3）迭代实现redis数组的赋值操作;
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int length = nums.length;
        int[] redis = new int[length];
        // 假设f(i)表示的是 从标号为0的房屋开始到标号为i的房屋为止最多能够偷取到的财物
        // 状态转移方程 ：f(i) = max(f(i - 1) , f(i - 2) + nums[i]);
        // ===> 即，其中的隐性条件为 i >= 2
        redis[0] = nums[0];
        // 即小偷有两个选择（进入房屋0/1偷窃）,即选择价值较大的房屋进行偷窃;
        if(length >= 2){
            // length的取值范围 [1 , 100],可能有且仅有一个房屋的特殊情况
            redis[1] = Math.max(nums[0] , nums[1]);
        }
        // 迭代，实现动态规划;
        for(int i = 2 ; i < length ; i++){
            redis[i] = Math.max(redis[i - 1] , redis[i - 2] + nums[i]);
        }
        return redis[length - 1];
    }
    /**
     * 分析 ：
     * （1）时间复杂度 ：O（n）;
     * （2）空间复杂度 ：O（n）；
     */
}
